package leetcode;
/**
 * 377.组合总和Ⅳ
 * 给定⼀个由正整数组成且不存在重复数字的数组，找出和为给定⽬标正整数的组合的个数。 示例:
 * nums = [1, 2, 3]
 * target = 4
 *
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。因此输出为 7。
 */
public class Num_377 {
    //转为完全背包问题,和上一个硬币问题的区别：这道题考虑序列的顺序
    public int combinationSum4(int[] nums, int target) {
        //又是一个完全背包问题，但是顺序不同被视为不同的组合
        //dp[i][j]表示前i个元素凑出j的组合数
        int[][] dp = new int[nums.length + 1][target + 1];
        //初始化
        for(int i = 0; i <= nums.length; i++){
            //只有一种方法可以凑出0，就是一个都不选
            dp[i][0] = 1;
        }
        //先遍历元素
        for(int i = 1; i <= nums.length; i++){
            //再遍历背包容量
            for(int j = 1; j <= target; j++){
                /**
                 * 此时就不是常规的考虑选不选第i个这两种情况了
                 * 而是考虑组合的顺序，即选择的最后一个元素是哪个
                 */
                for(int k = 1; k <= i; k++){
                    //如果最后一个元素是第k个元素,
                    if(nums[k - 1] <= j){
                        //除了最后一个元素是第k个外，其余元素还是从1~i中选
                        dp[i][j] += dp[i][j - nums[k-1]];
                    }
                }
            }
        }
        return dp[nums.length][target];
    }
}